package cn.zhaoyuening.algorithms.dynamic;

import java.util.Map;
import java.util.Random;

/**
 * Created by Buynow on 2017/7/28.
 */
public class SteelCutting {
    int len ;
    int[] priceArr;
    Integer[] maxCostArr;
    public SteelCutting(int len, int[] priceArr) {
        this.len = len;
        this.priceArr = priceArr;
        maxCostArr = new Integer[len];
    }

    public Integer getMaxCost() {
        return maxCost(this.len, priceArr);
    }

    public void clean() {
        maxCostArr = new Integer[len];
    }

    public Integer getMaxCost2() {
        return maxCost2(this.len, priceArr);
    }

    public Integer maxCost(int len, int[] priceArr) {
        if (maxCostArr[len-1] != null) {
            return maxCostArr[len-1];
        }
        int max = 0;
        int r = 0;
        for (int i=1;i<=(len/2);i++){
            r = maxCost(i, priceArr) + maxCost(len - i, priceArr);
            max = Math.max(r, max);
        }
        max = Math.max(priceArr[len-1],max);
        maxCostArr[len - 1] = max;
        return max;
    }

    public Integer maxCost2(int len, int[] priceArr) {
        if (len == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        for(int i=1;i<=len;i++) {
            max = Math.max(max, priceArr[i - 1] + maxCost2(len - i, priceArr));
        }
        return max;
    }

    public static void main(String[] args) {
        int[] priceArr = new int[100];
        Random random = new Random();
        for (int i=0;i<priceArr.length;i++) {
            priceArr[i] = random.nextInt((i + 5)*10);
        }
        SteelCutting cutting = new SteelCutting(20, priceArr);
        long l = System.currentTimeMillis();
        System.out.println(cutting.getMaxCost());
        System.out.println(System.currentTimeMillis()-l);
        cutting.clean();
        l = System.currentTimeMillis();
        System.out.println(cutting.getMaxCost2());
        System.out.println(System.currentTimeMillis()-l);

    }
}
